#define _CRT_SECURE_NO_WARNINGS 1

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* slow = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tall = (struct ListNode*)malloc(sizeof(struct ListNode));
    slow->next = NULL;
    tall->next = NULL;

    if (!head)
    {
        return head;
    }
    struct ListNode* pcur = head;
    struct ListNode* slpcur = slow;
    struct ListNode* tapcur = tall;
    while (pcur)
    {
        if (pcur->val < x)
        {
            slpcur->next = pcur;
            slpcur = pcur;
        }
        else
        {
            tapcur->next = pcur;
            tapcur = pcur;
        }
        pcur = pcur->next;
    }
    slpcur->next = tall->next;
    tapcur->next = NULL;

    return slow->next;
}
